////////由于链表的头节点可能会被删除，因此我们需要额外使用一个空节点newhead指向链表的头节点。
////////newhead是不动的，current=newhead 只让current->next和current->next->next不断向后遍历
////////这样就不会断了联系，遇见相同的往后找不相同的，遇见不相同的指向它然后再判断它之后的
////////链表的改变是由于current在发力，current在纠正重复的节点并改变指向
#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 删除重复节点的函数
ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head;

    ListNode* newhead = new ListNode;
    newhead->next = head;
    ListNode* current = newhead;

    while (current->next && current->next->next) {
        if (current->next->val == current->next->next->val) {
            int x = current->next->val;
            while (current->next && current->next->val == x) {
                current->next = current->next->next;
            }
        }
        else {
            current = current->next;
        }
    }
    ListNode* result = newhead->next;
    delete newhead; // 释放虚拟头节点
    return result;
}

// 创建链表的辅助函数
ListNode* createLinkedList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < n; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// 打印链表的辅助函数
void printLinkedList(ListNode* head) {
    ListNode* current = head;
    while (current) {
        cout << current->val;
        if (current->next) cout << " -> ";
        current = current->next;
    }
    cout << " -> nullptr" << endl;
}

// 释放链表内存的辅助函数
void deleteLinkedList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    cout << "=== 测试删除链表重复节点 ===" << endl;

    // 测试用例1: 有重复的普通情况
    cout << "\n测试用例1: 1->2->3->3->4->4->5" << endl;
    int arr1[] = { 1, 2, 3, 3, 4, 4, 5 };
    ListNode* list1 = createLinkedList(arr1, 7);
    cout << "原链表: ";
    printLinkedList(list1);

    ListNode* result1 = deleteDuplicates(list1);
    cout << "去重后: ";
    printLinkedList(result1);

    // 测试用例2: 开头就有重复
    cout << "\n测试用例2: 1->1->1->2->3" << endl;
    int arr2[] = { 1, 1, 1, 2, 3 };
    ListNode* list2 = createLinkedList(arr2, 5);
    cout << "原链表: ";
    printLinkedList(list2);

    ListNode* result2 = deleteDuplicates(list2);
    cout << "去重后: ";
    printLinkedList(result2);

    // 测试用例3: 所有元素都重复
    cout << "\n测试用例3: 2->2->2->2" << endl;
    int arr3[] = { 2, 2, 2, 2 };
    ListNode* list3 = createLinkedList(arr3, 4);
    cout << "原链表: ";
    printLinkedList(list3);

    ListNode* result3 = deleteDuplicates(list3);
    cout << "去重后: ";
    printLinkedList(result3);

    // 测试用例4: 没有重复元素
    cout << "\n测试用例4: 1->2->3->4->5" << endl;
    int arr4[] = { 1, 2, 3, 4, 5 };
    ListNode* list4 = createLinkedList(arr4, 5);
    cout << "原链表: ";
    printLinkedList(list4);

    ListNode* result4 = deleteDuplicates(list4);
    cout << "去重后: ";
    printLinkedList(result4);

    // 测试用例5: 空链表
    cout << "\n测试用例5: 空链表" << endl;
    ListNode* list5 = nullptr;
    cout << "原链表: ";
    printLinkedList(list5);

    ListNode* result5 = deleteDuplicates(list5);
    cout << "去重后: ";
    printLinkedList(result5);

    // 测试用例6: 单个节点
    cout << "\n测试用例6: 单个节点 5" << endl;
    int arr6[] = { 5 };
    ListNode* list6 = createLinkedList(arr6, 1);
    cout << "原链表: ";
    printLinkedList(list6);

    ListNode* result6 = deleteDuplicates(list6);
    cout << "去重后: ";
    printLinkedList(result6);

    // 测试用例7: 交替重复
    cout << "\n测试用例7: 1->1->2->2->3->3" << endl;
    int arr7[] = { 1, 1, 2, 2, 3, 3 };
    ListNode* list7 = createLinkedList(arr7, 6);
    cout << "原链表: ";
    printLinkedList(list7);

    ListNode* result7 = deleteDuplicates(list7);
    cout << "去重后: ";
    printLinkedList(result7);

    // 释放内存
    deleteLinkedList(result1);
    deleteLinkedList(result2);
    deleteLinkedList(result3);
    deleteLinkedList(result4);
    deleteLinkedList(result5);
    deleteLinkedList(result6);
    deleteLinkedList(result7);

    cout << "\n=== 所有测试完成 ===" << endl;

    return 0;
}